#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int value;

	struct node* left;
	struct node* right;
}tree;

tree * insert (tree * root, int value)
{
	tree *node;
	if (!root) {
		node = malloc(sizeof(tree));
		node->value = value;
		node->left = node->right = NULL;
		return node;
	}

	tree *active, *prev;
	active = root;

	while (active) {

		prev = active;

		if (active->value < value)
			active = active->right;
		else if (active->value > value)
			active = active->left;
		else {
			printf ("%d element already exists\n", value);
			return root;
		}
	}

	node = malloc(sizeof(tree));
	node->value = value;
	node->left = node->right = NULL;

	if (prev->value < value)
		prev->right = node;
	else
		prev->left = node;

	return root;
}

tree * search (tree *root, int value)
{
	if (!root) {
		printf ("Tree is empty\n");
		return NULL;
	}

	tree *active;
	active = root;

	while (active) {

		if (active->value < value)
			active = active->right;
		else if (active->value > value)
			active = active->left;
		else if (active->value == value) {
			printf ("match found %d\n", value);
			return active;
		}
	}

	printf ("element %d not found\n", value);

	return NULL;
}

tree * delete (tree *root, int value)
{
	if (!root) {
		printf ("delete call for element [%d] in an empty tree\n", value);
		return NULL;
	}

	tree *active, *prev = NULL;
	active = root;

	while (active) {

		if (active->value == value)
			break;

		prev = active;

		if (active->value < value)
			active = active->right;
		else if (active->value > value)
			active = active->left;
	}

	if (!active) {
		printf ("element not found in the tree\n");
		return root;
	}

	if (!active->left && !active->right) {
		// Leaf Node
		if (prev) {
			if (prev->left == active)
				prev->left = NULL;
			else
				prev->right = NULL;

			printf ("element %d deleted\n", value);
			free (active);
			return root;
		} else {
			printf ("root was the element we searched for and there are no other elements in the tree. emptied the tree.\n");
			printf ("element %d deleted\n", value);
			free (active);
			return NULL;
		}
	}

	// Only left child
	if (active->left && !active->right) {
		if (prev) {
			if (prev->left == active)
				prev->left = active->left;
			else
				prev->right = active->left;

			printf ("element %d deleted\n", value);
			free (active);
			return root;
		} else {
			tree *temp;

			printf ("root was the element we searched for. making the left child as the new root\n");
			printf ("element %d deleted\n", value);
			temp = active->left;
			free (active);
			return temp;
		}
	}

	//Only right child
	if (!active->left && active->right) {
		if (prev) {
			if (prev->left == active)
				prev->left = active->right;
			else
				prev->right = active->right;

			printf ("element %d deleted\n", value);
			free (active);
			return root;
		} else {
			tree *temp;

			printf ("root was the element we searched for. making the right child as the new root\n");
			printf ("element %d deleted\n", value);
			temp = active->left;
			free (active);
			return temp;
		}
	}

	//Both children exist
	tree *temp;

	temp = active->right;
	while (temp->left) {
		prev = temp;
		temp = temp->left;
	}

	active->value = temp->value;
	if (prev) {
		prev->left = NULL;
	} else {
		active->right = temp->right;
	}
	printf ("element %d deleted\n", value);
	free (temp);

	return root;
}



typedef struct lnode {
	int value;

	struct lnode *next;
}list;

list * prepend (list *head, int value)
{
	list *node = malloc (sizeof(list));

	node->value = value;
	node->next = head;

	return node;
}


void convert_tree_to_array_of_linked_lists_at_each_level (tree *t, list*a[], int level)
{
	if (!t)
		return;

	a[level] = prepend (a[level], t->value);

	if (t->left)
		convert_tree_to_array_of_linked_lists_at_each_level (t->left, a, level + 1);

	if (t->right)
		convert_tree_to_array_of_linked_lists_at_each_level (t->right, a, level + 1);

	return;
}

int main ()
{
	tree *t;

	t = insert (NULL, 4);
	t = insert (t, 2);
	t = insert (t, 9);
	t = insert (t, 1);
	t = insert (t, 3);
	t = insert (t, 5);
	t = insert (t, 12);

	list *a[512] = {0}, *tmp;

	convert_tree_to_array_of_linked_lists_at_each_level (t, a, 0);

	// Printing the linked lists
	int i;
	for (i = 0; a[i]; i++) {
		tmp = a[i];
		while (tmp) {
			printf ("%d\t", tmp->value);
			tmp = tmp->next;
		}
		printf ("\n");
	}

	return 0;
}
